package fun.ticsmyc.question.dp;

import java.util.Arrays;

/**
 * 如果暴力枚举所有字串  时间复杂度为O(N^2)
 * 判断字串是否回文  时间复杂度O(N)
 * 总体复杂度为O(N^3)
 *
 * 可以使按照类似于判断回文子序列的方式，用dp优化到总体O(N^2)
 * @author Ticsmyc
 * @date 2021-03-07 21:47
 */
public class 枚举回文子串 {

    public boolean[][] judge(String s){
        char[] str= s.toCharArray();
        int n =s.length();

        boolean[][] dp = new boolean[n][n];
        /**
         * i j为一个子串
         * dp[i][j]表示这个子串是否为回文
         * 初始化为true， 且i>=j时全部为true
         */
        for(int i=0;i<dp.length;++i){
            Arrays.fill(dp[i],true);
        }
        /**
         * 状态转移方程为
         * dp[i][j] = dp[i+1][j-1] &&(str[i] == str[j])
         */
        for(int i=n-2;i>=0;--i){
            for(int j=i+1;j<n;++j){
                dp[i][j]= dp[i+1][j-1]&&(str[i]==str[j]);
            }
        }
        return dp;
    }
}
